package No1_100.No61_70.ClimbingStairs_70;

public class Solution {
	
	public int climbStairs(int n) {
        int[] count = new int[n + 1];
        count[0] = 1;
        count[1] = 1;
        for (int i = 2; i <= n; i++) {
			count[i] = count[i-1]+count[i-2];
		}
        return count[n];
    }
    public int climbStairs1(int n) {
        if(n == 1){
            return 1;
        }
        if(n == 2){
            return 2;
        }
        if(n > 2){
            return climbStairs(n-1)+climbStairs(n-2);
        }else{
            return 0;
        }
    }
    public static void main(String[] args) {
		Solution solution = new Solution();
		System.out.println(solution.climbStairs(5));
	}
}
